Searching and sorting
Table of Contents
This assignment is to be done individually. You can talk to other people in the class, me (Dave), the prefect, and lab assistants for ideas and to gain assistance. You can help each other debug programs, if you wish. The code that you write should be your own, however, and you shouldn’t hand a printout of your program to others. See the course syllabus for more details or just ask me if I can clarify.
You can use whatever software you like to create this document, but you should submit it as a PDF. This is good practice for transmitting electronic work: sending word processor documents (such as Microsoft Word, etc) does not guarantee that your reader will see the layout in the same way that you do. Ask for help if you need help generating a PDF; you will lose a point if you do not do so.
1. Linear vs. binary search
When measuring the worst case performance of sequential and binary search, we did so by counting the number of times we compared the key (also known as the target) against data in the list. Why didn’t we do something simpler, like measuring running time with a stopwatch?
2. Key comparisons
In the case of quantifying how much work binary search takes, there’s actually a subtle distinction between
- counting “the number of times we see if the key equals an item in the list,” and
- counting “the number of times we make some kind of comparison between our key against an item in the list.”
Explain how the answer you would get for your worst-case count in the second case differs from the first case.
3. Selection sort
Here is a list of numbers:
[12, 6, 3, 9, 10, 4]
Show how selection sort would handle this list. Specifically, show what the list would look like each time the positions of two numbers are changed.
4. Insertion sort
Redo the above problem for insertion sort.
5. Merge sort
Here is another list of numbers:
[12, 6, 3, 9, 10, 4, 1, 20]
Show how merge sort would handle this list. Specifically, show a diagram similar to the ones I’ve been doing, or are shown in the reading.
6. Grading criteria:
- Exemplary: demonstrates complete or essentially complete capability on all of the above problems
- Meets expectations: demonstrates general capability on all of the above problems, but at least one problem has a significant error that goes beyond a surface mistake
- Partially meets expectations: some facility is demonstrated, but multiple notable gaps are shown
- Beginnings: minimal evidence is shown for the beginnings of success